1. Field of the Invention
The present invention relates to electronic devices, and, more specifically to a system for authenticating an accessory used with an electronic device.
2. Background of the Invention
Manufacturers of electronic devices (e.g. cellular telephones) have an interest in ensuring that accessories (e.g., batteries) operating with the devices meet the standards of the manufacturer. One way of doing this is to employ a system that authenticates accessories used with the manufactured devices.
To reduce the number of unauthorized accessories, certain relatively low-cost semiconductors enable an accessory to be authenticated by a device to which it is connected. These semiconductors typically contain a hashing function and a secret hashing key. To use such a system, both the authenticating device and the accessory have “pre-shared” knowledge of the secret hashing key. The authenticating device generates a seemingly random challenge message and sends it to the accessory. The accessory computes a hash over a combination of the secret hashing key, the received challenge message, and possibly additional padding data. Since the authenticating device knows the secret hashing key, it performs the same computation to determine the expected hash digest. The accessory returns the resulting digest value to the authenticating device, which compares an internally-calculated response to the response received from the accessory. If the expected and received hash digests match, then the device has been authenticated and normal operation of the device will be allowed. Such devices may be vulnerable because the authenticating device must store the secret hashing key value.
Another method of authentication uses public key encryption, that uses both a public key that is made publicly available and a private key that is stored only by the device. The public and private keys are inverses and are asymmetrical If the accessory were to store a private asymmetric key, the phone would send a random challenge to the accessory. The accessory would either encrypt or digitally sign the challenge using the private key and return it. The device would use a trusted public key either to decrypt the response and see if it matched what was sent, or to verify the signature on the response. However, implementing this in an accessory would add substantially to the cost of the accessory.
Certain devices lack the ability to store a key securely. Even in devices with a hardware-based capability of securing the value of the key, there is still a problem of how to provision the value of the key into the accessories in a secure manner.
There are several different techniques used to disable authentication algorithms in devices, including collision attacks and preimage attacks. A collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e., a hash collision. A hash collision is a situation that occurs when two distinct inputs into a hash function produce identical outputs. One desirable property of cryptographic hash functions is that it may be impractical to find a collision. Most hash functions have potential collisions, but with good hash functions they occur less often than with bad ones.
There are two types of preimage attacks: (1) a first preimage attack: given a hash h, find a message m such that hash(m)=h; and (2) a second preimage attack: given a fixed message m1, find a message m2 such that hash(m2)=hash(m1). A preimage attack differs from a collision attack in that there is a fixed hash or message that is being attacked. These attacks can be used by a sophisticated attacker to determine the value of the hashing key, or at least determine the expected response to a challenge, from such devices. Doing so could allow an attacker to make cloned or counterfeit devices.
Therefore, there is a need for a system that authenticates an accessory in which a key to authenticating an accessory cannot be derived from either the accessory or the device with which the accessory is used.